//
//  LinkQueue.hpp
//  408数据结构
//
//  Created by Cai Yuanhao on 2022/3/26.
//

#ifndef LinkQueue_hpp
#define LinkQueue_hpp

#include <stdio.h>
#include<stdlib.h>
#endif /* LinkQueue_hpp */
typedef int Elemtype;
typedef struct LinkNode{
    Elemtype data;
    struct LinkNode * next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    Q.front->next=NULL;
}

bool IsEmpty(LinkQueue Q){
    if(Q.front==Q.rear){
        return true;
    }
    return false;
}

void Enqueue(LinkQueue &Q,Elemtype e){
    LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));
    s->data=e;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

bool Dequeue(LinkQueue &Q,Elemtype &e){
    if(IsEmpty(Q)){
        return false;
    }
    LinkNode *p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p){
        // 若原队列中只有一个节点，删除后变空；
        Q.rear=Q.front;
    }
    free(p);
    return true;
}